/**
 * The target of this genetic algorithm with a colony of four members is to
 * find the maximum value of the following function
 *                   f(x,y) = x^2 + y^2 - 2*x + y
 * with its domain being
 *                   x = {0,..,15}, y = {0,..,15}
 * On the other hand, an algorithm, selecting a random bit of the last four
 * best results to change, will run simultaneously as a comparation to the
 * genetic algorithm.
 *
 * Author:  David Qiu (david@davidqiu.com)
 * Website: http://www.davidqiu.com/
 * Date:    2014.5.26
 */

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;


// Option switches
#define INFO
//#define DEBUG


/**
 * @brief     Obtain the value of the estimation function.
 * @param x   The left parameter of the estimation function.
 * @param y   The right parameter of the estimation function.
 * @return    An int indicating the value of the estimation function.
 */
int est_func(int x, int y)
{
  return (x*x + y*y - 2 * x + y);
}


/**
* @brief     Obtain the value of the estimation function.
* @param colony_member   The colony member to be estimated.
* @return    An int indicating the value of the estimation function.
*/
int est_func(int colony_member)
{
  unsigned int x = (unsigned)colony_member;
  unsigned int y = (unsigned)colony_member;

  // Trim the tail of x
  x >>= 4;

  // Trim the head of y
  y <<= 28;
  y >>= 28;

  // Calculate the estimation value
  return est_func(x, y);
}


/**
 * @brief     Display the binary expression of a number.
 * @param num   The number to binaryze and display.
 */
void display_bits(int num)
{
  unsigned int mask = 0x80000000;
  
  for (int i = 0; i<32; ++i)
    printf((i % 8 == 0 && i != 0) ? (" %u") : ("%u"), (((num << i)&mask) == 0) ? (0) : (1));

  printf("\n");
}


/**
 * @brief       Change the bit of the input number at specific index.
 * @param num   The original number to change one bit.
 * @param idx   The index of the bit to be changed. {0,..,15}
 */
void change_bit(int& num, int idx)
{
  num = num^(1 << idx);
}


/**
 * @brief     Swap the value of two numbers.
 * @param a   The first number of the swapping.
 * @param b   The second number of the swapping.
 */
void swap(int& a, int& b)
{
  int tmp = a;
  a = b;
  b = tmp;
}


/**
 * @brief     Try to insert a number into a colony, and keep the members with
 *            higher priority remaining in the colony after the insertion.
 * @param colony   The colony to try insertion.
 * @param candidate   The candidate colony member to be inserted into the colony.
 */
void priority_insert(int colony[], int candidate)
{
  int min_val = est_func(colony[0]);
  int min_idx = 0;

  // Find the index of minimum estimation value
  for (int i = 1; i < 4; ++i)
  {
    if (est_func(colony[i]) < min_val)
    {
      min_val = est_func(colony[i]);
      min_idx = i;
    }
  }

  // Check the candidate
  if (est_func(candidate) > min_val)
  {
    colony[min_idx] = candidate;
  }
}


/**
 * @brief     Obtain the maximum estimation value of a colony.
 * @param colony   The colony to be estimated.
 * @return    An int indicating the maximum estimation value within the 
 *            input colony.
 */
int get_max_est_val(int colony[])
{
  int max_val = est_func(colony[0]);
  for (int i = 1; i < 4; ++i)
  {
    if (est_func(colony[i]) > max_val) max_val = est_func(colony[i]);
  }

  return max_val;
}


/**
 * @brief     Run the algorithm of changing random bit and succeeding the
 *            best four results.
 * @param init_colony   The initial values of the colony, which is represented
 *            by a int array of size of four entries.
 * @return    An int indicating the number of steps gone through before the
 *            stable result achieved.
 */
int run_random_bit_algorithm(int init_colony[])
{
  int colony[4];
  int tmp_colony[4];
  int max_val;
  int stable_count = 0;
  int step_count = 0;

  // Initialize the colony and maximum estimation value
  for (int i = 0; i < 4; ++i) colony[i] = init_colony[i];
  max_val = get_max_est_val(colony);

  // Run the algorithm until stable value achieved
  while (stable_count < 10)
  {
    // Remember the previous colony
    for (int i = 0; i < 4; ++i) tmp_colony[i] = colony[i];

    // Change a random bit of each colony member
    for (int i = 0; i < 4; ++i) change_bit(colony[i], rand() % 8);

    #ifdef INFO
    printf("[Ramdom Bit Algorithm] %d\n", step_count + 1);
    for (int i = 0; i < 4; ++i)
    {
      #ifdef DEBUG
      display_bits(colony[i]);
      #endif
      printf("(%d, %d) = %d\n", (((unsigned)colony[i]) >> 4), (((unsigned)(colony[i] << 28)) >> 28), est_func(colony[i]));
    }
    for (int i = 0; i < 4; ++i)
    {
      #ifdef DEBUG
      display_bits(tmp_colony[i]);
      #endif
      printf("(%d, %d) = %d\n", (((unsigned)tmp_colony[i]) >> 4), (((unsigned)(tmp_colony[i] << 28)) >> 28), est_func(tmp_colony[i]));
    }
    #endif

    // Keep the best four results
    for (int i = 0; i < 4; ++i) priority_insert(colony, tmp_colony[i]);

    #ifdef INFO
    for (int i = 0; i < 4; ++i)
    {
      #ifdef DEBUG
      display_bits(colony[i]);
      #endif
      printf("SELECT (%d, %d) = %d\n", (((unsigned)colony[i]) >> 4), (((unsigned)(colony[i] << 28)) >> 28), est_func(colony[i]));
    }
    #endif

    // Refresh the state variables
    ++step_count;
    if (max_val == get_max_est_val(colony))
    {
      ++stable_count;
      #ifdef INFO
      printf("(max_val = %d, stable = %d)\n", max_val, stable_count);
      #endif
    }
    else
    {
      stable_count = 0;
      max_val = get_max_est_val(colony);
    }

    #ifdef INFO
    printf("\n");
    #endif

    #ifdef DEBUG
    system("pause");
    #endif
  }

  // Return the steps it takes to achieve the stable state
  return step_count;
}


/**
* @brief     Run the genetic algorithm.
* @param init_colony   The initial values of the colony, which is represented
*            by a int array of size of four entries.
* @return    An int indicating the number of steps gone through before the
*            stable result achieved.
*/
int run_genetic_algorithm(int init_colony[])
{
  int colony[4];
  int tmp_colony[4];
  int max_val;
  int stable_count = 0;
  int step_count = 0;


  // Initialize the colony and the maximum estimation value
  for (int i = 0; i < 4; ++i) colony[i] = init_colony[i];
  max_val = get_max_est_val(colony);

  // Run the algorithm until stable state achieved
  while (stable_count < 10)
  {

  }

}


/**
 * @brief     The entrance of the program logic.
 */
int main()
{
  int init_colony[4];
  int steps_random_bit_algorithm;
  
  // Plant the random seed
  srand(0);

  // Generate the initial colony
  for (int i = 0; i < 4; ++i) init_colony[i] = rand() % 16;

  // Run the ramdom bit algorithm
  steps_random_bit_algorithm = run_random_bit_algorithm(init_colony);

  // Summarize the performance
  printf("[Ramdom Bit Algorithm] STEP COUNT = %d\n", steps_random_bit_algorithm);


  system("pause");
  return 0;
}

